package com.leetcode.partition7;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/9/12 8:45
 */
public class LC678有效的括号字符串 {

    public static boolean checkValidString(String s) {
        return greedy(s.toCharArray());
    }

    public static void main(String[] args) {
        System.out.println(checkValidString("(*))"));
//        System.out.println(checkValidString("(((*(*"));
    }

    /**
     * 从左到右遍历字符串，遍历过程中，如果遇到左括号，则未匹配的左括号数量加1；如果遇到右括号，则未匹配的左括号数量减1；
     * 如果遇到*，此时未匹配的左括号数量可能加1、减1或者不变
     * 在遍历的过程中维护未匹配的左括号数量可能的最小值和最大值，根据遍历到的字符更新最小值和最大值：
     * 如果遇到左括号，minCount和maxCount都加1
     * 如果遇到右括号，minCount和maxCount都减1
     * 如果遇到*，minCount-=1，maxCount+=1
     * 任何情况，未匹配的左括号都应该为非负，因此当最大值为负数时，说明没有左括号可以和右括号匹配
     * 当最小值为0时，不应将最小值继续减少，以确保最小值非负
     * 遍历结束时，所有的左括号都应该和右括号匹配，因此只有当最小值为0时，s才是有效串
     */
    private static boolean greedy(char[] word) {
        int minCount = 0, maxCount = 0;
        for (int i = 0; i < word.length; i++) {
            if (word[i] == '(') {
                minCount++;
                maxCount++;
            } else if (word[i] == ')') {
                minCount = Math.max(0, minCount - 1);
                maxCount--;
                if (maxCount < 0) return false;
            } else {
                minCount = Math.max(0, minCount - 1);
                maxCount++;
            }
        }
        return minCount == 0;
    }

    private static boolean stackSolution(char[] word) {
        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> asteriskStack = new Stack<>();
        for (int i = 0; i < word.length; i++) {
            if (word[i] == '(') {
                leftStack.push(i);
            } else if (word[i] == '*') {
                asteriskStack.push(i);
            } else {
                if (!leftStack.isEmpty()) leftStack.pop();
                else if (!asteriskStack.isEmpty()) asteriskStack.pop();
                else return false;
            }
        }
        //如果星号栈还有元素且左括号还有元素，将星号栈中的符号看做右括号
        while (!leftStack.isEmpty() && !asteriskStack.isEmpty()) {
            int left = leftStack.pop();
            int asterisk = asteriskStack.pop();
            if (left > asterisk) return false;          //星号在左括号前面
        }
        return leftStack.isEmpty();
    }

    /**
     * dp[i][j]：字符串从下标i到j的子串是否是有效括号字符串，其中0<=i<=j<=n
     * 当子串长度为1时，只有是*时，才是有效子串，此时的子串可以看做空串
     * 当子串长度2时，只有()、(*、*)、**，才是有效子串，此时的子串可以看做()
     * 当子串长度大于2时，需要根据子串的首尾字符以及中间的字符判断子串是否有效，此时j-i>=2，若满足以下任何一个条件，即有dp[i][j]=true
     *     如果s[i]和s[j]分别为左括号或右括号，或者都为*时。则当dp[i+1][j-1]=true时，有dp[i][j]=true，此时s[i]和s[j]分别可以看做左括号和右括号
     *     如果存在i<=k<j使得dp[i][k]和dp[k+1][j]都为true，则dp[i][j]=true，因为字符串的下标范围[i, k]和[k + 1, j]的子串分别为有效的括号字符串，
     *     则两个子串拼接后的子串也是有效串，范围[i, j]
     * 类似于516.最长回文子序列
     */
    private static boolean dynamicProgramming(char[] word) {
        if (word.length == 0 || (word.length == 1 && word[0] == '*')) return true;
        if (word[word.length - 1] == '(') return false;
        boolean[][] dp = new boolean[word.length][word.length];
        for (int i = 0; i < word.length; i++) {
            if (word[i] == '*') dp[i][i] = true;            //长度为1时，初始化*，全是*的看做空字符串，满足条件
            //当子串长度2时，只有()、(*、*)、**，才是有效子串，此时的子串可以看做()
            if (i >= 1 && (word[i - 1] == '(' || word[i - 1] == '*') && (word[i] == ')' || word[i] == '*')) {
                dp[i - 1][i] = true;
            }
        }
        //长度大于2的子串
        for (int i = word.length - 3; i >= 0; i--) {
            for (int j = i + 2; j < word.length; j++) {
                if ((word[i] == '(' || word[i] == '*') && (word[j] == ')' || word[j] == '*')) {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                //如果存在i<=k<j使得dp[i][k]和dp[k+1][j]都为true，则dp[i][j]=true，因为字符串的下标范围[i, k]和[k + 1, j]的子串分别为有效的括号字符串，
                //则两个子串拼接后的子串也是有效串，范围[i, j]
                for (int k = i; k < j && !dp[i][j]; k++) {
                    dp[i][j] = dp[i][k] && dp[k + 1][j];
                }
            }
        }
        Arrays.stream(dp).forEach(item -> System.out.println(Arrays.toString(item)));
        return dp[0][word.length - 1];
    }
}
